package 分类.队列和栈;

import java.util.Stack;
/*
因为求的是连续的，所以就得引入动态规划了
 */
public class 最长有效括号 {
    public static int longestValidParentheses(String s) {
       int res=0;
       int[] dp=new int[s.length()];
       Stack<Integer> stack=new Stack();
       for (int i=0;i<s.length();i++){
           if(s.charAt(i)=='('){
               stack.push(i);
               dp[i]=0;
           }else {
               if(!stack.isEmpty()){
                   int leftIndex=stack.pop();
                   int len;
                   if(leftIndex==0){
                       len=i+1-leftIndex;
                   }else {
                       len=i+1-leftIndex+dp[leftIndex-1];
                   }

                   dp[i]=len;
               }else {
                   dp[i]=0;
               }
           }
       }
        for (int i : dp) {
            res=Math.max(res,i);
        }
       return res;
    }

    public static void main(String[] args) {
        String s="()(()";
        System.out.println("longestValidParentheses(s) = " + longestValidParentheses(s));
    }


}
